package list;

// 线性表的性质
// 保证插入元素有序 且可以重复
// 底层通过数组实现 ArrayList
public class ArrayList {
    private long[] values; // 元素数组
    private int size;      // 实际元素数量
    private int capacity;  // 容量
    private static final double balance = 0.75;//平衡系数

    public int getSize() {
        return size;
    }

    // 不指定容量 默认为 10 个元素
    public ArrayList() {
        this.size = 0;
        this.capacity = 10;
        this.values = new long[this.capacity];
    }
    // 指定容量
    public ArrayList(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        this.values = new long[this.capacity];
    }

    // 用于动态扩容
    private void check(){
        if((double)(size/capacity) >= balance){
            //需要扩容
            // 步骤 0. 申请一个 原来两倍大的空间
            // 1.将数组中的元素copy 到新的数组中去
            // this.values = temp;
            // this.capacity = this.capacity*2;
            long[] temp = new long[capacity*2];
            System.arraycopy(values,0,temp,0,size);
            this.capacity = this.capacity*2;
            this.values = temp;
        }
        return ;
    }

    // 增 删 查 改
    // 增 （不指定位置 默认尾插）
    public void add(long value){
        check();
        this.values[size++] = value;
        return ;
    }

    // 指定位置插入
    public void add(int index,long value){
        if(index < 0 || index > size) {
            throw new ArrayIndexOutOfBoundsException("index : " + index);
        }
        check();
        for(int i = size; i > index; i--){
            this.values[i] = this.values[i-1];
        }
        this.values[index] = value;
        size++;
    }

    // 删除指定下标元素(并返回)
    public long delete(int index){
        if(index <= 0 || index >= size) {
            throw new ArrayIndexOutOfBoundsException("index : "+ index);
        }
        // 为了保持有序性
        // 只能 将后面元素左移
        long ans = values[index];
        for(int i = index; i < size - 1; i++){
            values[i] = values[i+1];
        }
        size--;
        return ans;
    }

    public void remove(long element){
        // 删除数组中值为 element 的元素
        int end = 0; //逻辑上新数组的起始下标
        for(int begin = 0; begin < size; begin++){
            if(values[begin] != element){
                values[end++] = values[begin];
            }
        }
        size = end;
        return ;
    }

    // 找到元素并返回元素第一次出现时的下标 没有该元素返回 -1;
    public int search(long element){
        if(size == 0) return -1;
        for(int i = 0; i < size; i++){
            if(values[i] == element){
                return i;
            }
        }
        return -1;
    }

}
